// 1.大数相加
const bigAdd = (a, b) => {
    const maxLen = Math.max(a.length, b.length);
    a = a.padStart(maxLen, 0);
    b = b.padStart(maxLen, 0);
    
    let curry = 0;
    let current = 0;
    let sum = "";

    for(let i = maxLen -1; i >= 0; i--){
        current = parseInt(a[i]) + parseInt(b[i]) + curry;
        curry = Math.floor(current / 10);
        sum = current % 10 + sum;
    }
    if(curry === 1){
        sum = "1" + sum;
    }
    return sum;
}

let a = "9007199254740991";      //16位数，JS中number类型的最大安全范围，超出可能损失精度
let b = "1234567899999999999";   //20位数


console.log(bigAdd(a, b)); 
console.log(9007199254740991 + 1234567899999999999);

// 2.带并发限制的fetch
function sendRequest(urls, max, callback) {
    let pending_count = 0;
    let idx = 0;

    while (pending_count < max)
        _fetch(urls[idx]);

    function _fetch(url) {
        if(!url) return;
        pending_count++;
        fetch(idx);
        pending_count--;
        idx++;

        _fetch(urls[idx]);
        pending_count || callback && callback();
    }
}

const fetch = (idx) => {
    return new Promise((resolve)=> {
        let timeout = Math.random() * 1e4;
        setTimeout(()=>{
            resolve(idx);
        }, timeout)
    })
}

// 二分查找
function binary_search(low, high, arr, key) {
    if(low > high) return -1;
    let mid = parseInt((low + high) / 2);

    while(low <=high) {
        if(arr[mid] === key)
            return mid;
        else if(arr[mid] > key) {
            high = mid -1;
            return binary_search(low, high, arr, key);
        }else if(arr[mid] < key) {
            low = mid + 1;
            return binary_search(low, high, arr, key);
        }
    }
}

// 发布订阅模式
function Subject() {
    this.observers = [];
}

Subject.prototype = {
    subscribe: function(observer, option){
        let {once, priority} = option;
        this.observers.push({observer, once, priority});
        this.observers.sort((a, b) => b.priority - a.priority );
    },

    unsubscribe: function(observerToRemove){
        this.observers = this.observers.filter(observer => {
            observer !== observerToRemove
        });
    },

    publish: function(data){
        const current = [...this.observers];
        current.forEach(observer => {
            Promise.resolve().then(() => {
                observer.observer(data);
            })

            if(current.once === true)
                this.unsubscribe(observer);
        })
    }
}

const subject = new Subject();
function onlyOnce(data){
    console.log('只执行一次', data);
}
subject.subscribe(onlyOnce,{once: true});
subject.publish('一次')


// 反转列表
const reverseList = (head) => {
    let cur = head;
    let next = head;
    let prev = null;

    while(cur) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }

    return prev;
}

function ListNode(val, next = null){
    this.val = val;
    this.next = next;
}

let head = new ListNode(1, new ListNode(2, new ListNode(3)));


// 防抖:事件在N秒后执行回调，如果在N秒内又被触发，会重新计时。
function debounce(fn, wait) {
    var timer = null;
    return function(...args){
        if(timer)
            clearTimeout(timer);
        timer = setTimeout(() => {
            fn.apply(this, args);
            timer = null;
        }, wait)
    }
}

// 节流: 事件在触发N秒后执行回调，N秒内触发无效
function throttle(fn, wait){
    var timer = null;
    return function(...args){
        if(!timer){
            timer = setTimeout(() => {
                fn.apply(this, args);
                timer = null;
            }, wait)
        }
    }
}

function throttle(fn, wait){
    var prev = Date.now();
    return function(...args){
        var now = Date.now();
        if(now - prev >= wait){
            fn.apply(this, args);
            prev = Date.now();
        }
    }
}

// 归并排序




// 函数柯利化
    const curry = (fn, ...args) => {
        return fn.length <= args.length ? fn(...args) :
        curry.bind(null, fn, ...args);
    }

    // 动态传入参数个数
    function dynamicCurry(fn){
        const args = [];

        function curried(...newArgs){
            args.push(...newArgs);
            return curried;
        }

        curried.end = () => {
            return fn(...args);
        }

        return curried;
    }


// 将数组转为树形结构
var menu_list = [{
    id: '1',
    menu_name: '设置',
    menu_url: 'setting',
    parent_id: 0
   }, {
    id: '1-1',
    menu_name: '权限设置',
    menu_url: 'setting.permission',
    parent_id: '1'
   }, {
    id: '1-1-1',
    menu_name: '用户管理列表',
    menu_url: 'setting.permission.user_list',
    parent_id: '1-1'
   }, {
    id: '1-1-2',
    menu_name: '用户管理新增',
    menu_url: 'setting.permission.user_add',
    parent_id: '1-1'
   }, {
    id: '1-1-3',
    menu_name: '角色管理列表',
    menu_url: 'setting.permission.role_list',
    parent_id: '1-1'
   }, {
    id: '1-2',
    menu_name: '菜单设置',
    menu_url: 'setting.menu',
    parent_id: '1'
   }, {
    id: '1-2-1',
    menu_name: '菜单列表',
    menu_url: 'setting.menu.menu_list',
    parent_id: '1-2'
   }, {
    id: '1-2-2',
    menu_name: '菜单添加',
    menu_url: 'setting.menu.menu_add',
    parent_id: '1-2'
   }, {
    id: '2',
    menu_name: '订单',
    menu_url: 'order',
    parent_id: 0
   }, {
    id: '2-1',
    menu_name: '报单审核',
    menu_url: 'order.orderreview',
    parent_id: '2'
   }, {
    id: '2-2',
    menu_name: '退款管理',
    menu_url: 'order.refundmanagement',
    parent_id: '2'
   }
]


// 将http header转换为JS对象
/**
 * --- 测试用例 ---
 * 
 * 输入：
 * `Accept-Ranges: bytes 
 * Cache-Control: max-age=6000, public
 * Connection: keep-alive
 * Content-Type: application/javascript`
 * 
 * 输出：
 * {
 *   "Accept-Ranges": "bytes",
 *   "Cache-Control": "max-age=6000, public",
 *   Connection: "keep-alive",
 *   "Content-Type": "application/javascript"
 * }
 */
const solution = (s) => {
    const res = {};
    const arr = s.split('\n');
    arr.forEach(item => {
        const temp = item.split(':');
        res[temp[0]] = temp[1];
    })
    return res;
}

console.log(solution(`Accept-Ranges: bytes 
Cache-Control: max-age=6000, public
Connection: keep-alive
Content-Type: application/javascript`))



// 快速排序
function quickSort(start, end, arr){
    if(end <= start) return;
    let pivot = arr[start];
    let left = start;
    let right = end;

    while(left <right){
        while(left < right && arr[right] >= pivot)
            right--;
        arr[left] = arr[right];
        while(left < right && arr[left] <= pivot)
            left++;
        arr[right] = arr[left]
    }
    arr[left] = pivot;
    quickSort(left+1, end, arr);
    quickSort(start,left-1,arr);
    return arr;
}


console.log(quickSort(0, 3, [1,3,2,4]))

// 冒泡排序
function bubbleSort(arr){
    for(let i = 0;i < arr.length - 1; i++){
        for(let j = 0; j < arr.length - i - 1;j++){
            if(arr[j] > arr[j+1])
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        }
    }
    return arr;
}
console.log(bubbleSort([1,3,2,4]));

// 判断是否是回文数
function isPalindrome(s) {
    return s.toString().split('').reverse().join('') === s.toString();
}

// 求出一个集合所有的子集
const subSets = (nums) => {
    const res = [];
    function dfs(index, path){
        res.push(path.slice());
        for(let i = index; i< nums.length; i++){
            path.push(nums[i]);
            dfs(i+1, path);
            path.pop();
        }
    }
    dfs(0, []);
    return res;
}

console.log(subSets([1, 2, 3]));

// 全排列
const permute = (nums) => {
    const res = [];
    const used = {};

    function dfs(path){
        if(path.length === nums.length){
            res.push(path.slice());
            return;
        }

        for(let num of nums){
            if(used[num]) continue;
            path.push(num);
            used[num] = true;
            dfs(path);
            path.pop();
            used[num] = false;
        }
    }
    
    dfs([]);
    return res;
}

let nums = [1,2,3];
console.log(permute(nums));


// 深拷贝
function deepCopy(obj){
    if(typeof obj !== 'object' && obj === null)
        return obj;
    const res = obj instanceof Array ? [] : {};
    for(let key in obj){
        if(obj.hasOwnProperty(key)){
            result[key] = deepCopy(obj[key]);
        }
    }
    return result;
}


// 实现千位分隔符
function numFormat(num){
    num = num.toString().split('.');
    let arr = num[0].split('').reverse();
    let res = [];
    for(let i = 0; i < arr.length; i++){
        if(i % 3 === 0 && i!==0)
            res.push(',');
        res.push(arr[i]);
    }
    res.reverse();
    if(num[0])
        res = res.join('').concat('.' + num[1])
    else
        res = res.join('')
    return res;
}

var num = 123456789453.231331;
console.log(numFormat(num));

// 实现字符串翻转
function reverse(s){
    return s.length <=1 ? s:
    reverse(s.slice(1) + s[0]);
}

// 实现trim方法
function myTrim(s) {
    const reg = /^\s+|\s+$/g;
    return s.replace(reg,"");
}
console.log(myTrim('  a '))

// 实现 setTimeout模拟setInterval
function mySetInterval(fn, wait){
    let res = {target: ''};
    function test(){
        fn();
        res.target = setTimeout(test, wait);
    }
    test();
    return res;
}

function myClearInterval(timer){
    clearTimeout(timer.target);
}

// 手写寄生组合继承

// 手写解析url
/**
 * --- 题目描述 ---
 * 
 * 实现一个函数，可以对 url 中的 query 部分做拆解，返回一个 key: value 形式的 object  
 * 
 * --- 实例 ---
 * 
 * 输入：'http://sample.com/?a=1&e&b=2&c=xx&d#hash' 
 * 输出：{a: 1, b: 2, c: 'xx', d: ''}  
 */

function getQueryObj(url){
    let queryObj = {};
    urlObj = new URL(url);
    urlObj.search.slice(1, urlObj.search.length)
    .split('&').forEach(item => {
        let arr = item.split('&');
        queryObj[arr[0]] = arr[1] || '';
    })
    return queryObj;
}

// 手写AJAX请求
const xhr = new XMLHttpRequest();
xhr.open('GET','http://www.example.com');
xhr.send(obj);
xhr.onreadystatechange = () => {
    if(xhr.readyState === 4){
        if(xhr.status >= 200 && xhr.status < 300){
            console.log(xhr.responseText);
        }else {
            console.log('请求失败');
        }
    }
}

// Promise封装AJAX
const p = new Promise((resolve, reject) => {
    const xhr = new XMLHttpRequest();
    xhr.send('GET', 'http://www.example.com');
    xhr.open(obj);
    xhr.onreadystatechange = () => {
        if(xhr.readyState === 4){
            if(xhr.status >=200 && xhr.status < 300){
                resolve(xhr.responseText);
            }else{
                reject(xhr.status);
            }
        }
    }
})

p.then((value) => {
    console.log(value);
}).catch((error)=>{
    console.error(error)
})


// LRU缓存
var LRUCache = class {
    constructor(capacity){
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key){
      let cache = this.cache;
      if(cache.has(key)){
        let temp = cache.get(key);
        cache.delete(key);
        cache.set(key, temp);
        return temp;
      }else{
        return -1;
      } 
    }

    put(key, value){
        let cache = this.cache;
        if(cache.has(key)){
            cache.delete(key);
        }else if(cache.size >= this.capacity){
            cache.delete(cache.keys().next().value);
        }
        cache.set(key, value);
    }
}
// 手写apply
Function.prototype.myApply = function(context){
    if(typeof this !== 'function')
        throw new TypeError('Error');
    let result = null;
    context = context || window;
    context.fn = this;
    if(arguments[1]){
        result = context.fn(...arguments[1]);
    }else{
        result = context.fn();
    }
    delete context.fn;
    return result;
}

// 手写call
Function.prototype.myCall = function(context) {
    if(typeof this !== 'function')
        throw new TypeError('error');
    let args = [...arguments].slice(1);
    context = context || window;
    context.fn = this;
    var result = context.fn(...args)
    delete context.fn;
    return result;
}
// 手写bind
Function.prototype.myBind = function(context) {
    if(typeof this!== 'function'){
        throw new TypeError('Error');
    }
    context = context || window;
    context.fn = this;
    var args = [...arguments].slice(1);
    return function Fn(){
        var result = context.fn.apply(this instanceof Fn ? this : context, args.concat(...arguments));
        delete context.fn;
        return result;
    }
}

// 手写instanceof
function myInstanceof(leftValue, rightValue) {
    let rightProto = rightValue.prototype;
    leftValue = leftValue.__proto__;
    while(true) {
        if(leftValue === null)
            return false;
        if(leftValue === rightProto)
            return true;
        leftValue = leftValue.__proto__;
    }
}

// 手写JSONP
    // 前端代码
    function handleRes(data) {
        console.log("拿到的数据", data);
        document.body.innerHTML += `<p>姓名: ${data.name}, 年龄: ${data.age}, 时间: ${data.time}</p>`;
    }

    function loadJSONP() {
        const script = document.createElement('script');
        script.src = `http://localhost:3000/jsonp?callback=handleRes`;
        document.body.appendChild(script);
    }

    setTimeInterval(loadJSONP, 3000);

    // 服务端代码
    const express = require('express');
    const app = express();

    app.get('/jsonp', (req, res) => {
        const callback = req.query.callback;
        if(!callback) return res.status(400).send('Missing callback');
        const user = {
            name: 'Tom',
            age: Math.floor(Math.random() * 30 + 20), // 动态年龄
            time: new Date().toLocaleTimeString()     // 动态时间
        };
        res.setHeader('Content-type','application/javascript');
        res.send(`${callback}(${JSON.stringify(user)})`)
    });

    app.listen(3000, () => {
        console.log('JSONP server running on http://localhost:3000');
    });

// 手写new操作符
function myNew() {
    var obj = {};
    var Constructor = [].shift().call(arguments);
    obj.__proto__ = Constructor.prototype;
    var ret = Constructor.apply(obj, arguments);
    return typeof ret === 'object' ? ret : obj;
}

// 手写Promise.all
const myPromiseAll = (promises) => {
    return new Promise((resolve, reject) => {
        if(!Array.isArray(promises))
            return reject(new TypeError('arguments must be an array'))
        var resolvedCounter = 0;
        var promiseNum = promises.length;
        var resolvedValues = new Array(promiseNum); 
        for(let i = 0; i < promises.length; i++){
            Promise.resolve(promises[i]).then(
                value => {
                    resolvedCounter++;
                    resolvedValues[i] = value;
                    if(promiseNum === resolvedCounter) 
                        return resolve(resolvedValues)
                },
                reason => {
                    return reject(reason);
                }
            )
        }
    })
}

// 手写Promise
const PENDING ='pending';
const FULFILLED = 'fulfilled';
const REJECTED = 'rejected';

function Promise(executor) {
    let self = this;
    this.status = PENDING;
    self.onFulfilled = [];
    self.onRejected = [];

    function resolve(){}

    function reject(reason){}

    try {
        executor(resolve, reject)
    } catch(e) {
        reject(e);
    }

    Promise.prototype.then() = function(){}
}

// 手写Promise.race
const myRace = (promises) => {
    return new Promise((resolve, reject) => {
        for(let p of promises) {
            Promise.resolve(p).then(
                value => {
                    resolve(value);
                },
                reason => {
                    reject(reason);
                }
            )
        }
    })
}

// 手写map
function myMap(arr, mapCallback){
    if(!Array.isArray(arr) || !arr.length || typeof mapCallback !== 'function')
        return [];
    else {
        let result = [];
        for(let i = 0; i < arr.length; i++)
            result.push(mapCallback(arr[i], i, arr));
        return result;
    }
}

// 手写 reduce
function reduce(arr, reduceCallback, initialValue){
    if(!Array.isArray(arr) || !arr.length || typeof reduceCallback !== 'function')
        return [];
    else {
        let hasInitialValue = initialValue !== undefined;
        let result = hasInitialValue ? initialValue : arr[0];
        for(let i = hasInitialValue ? 1 : 0; i < arr.length; i++)
            result = reduceCallback(result, arr[i], i, arr);
        return result;
    }
}

// 手写filter
function filter(arr, filterCallback){
    if(!Array.isArray(arr) || !arr.length || typeof filterCallback !== 'function')
        return [];
    else {
        let result = [];
        for(let i = 0; i < arr.length; i++){
            if(filterCallback(arr[i], i, arr))
                result.push(arr[i])
        }
        return result;
    }
}

// 找出不含有重复字符的最长子串长度
const lengthOfLongestSubstring = (s) => {
    let window = {};
    let left = 0, right= 0;
    let maxLen = 0;
    while(right < s.length){
        let current = s[right];
        window[current] ? window[current]++ : window[current] = 1;
        right++;
        while(window[current] > 1){
            let now = s[left];
            left++;
            window[now]--;
        }
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

// 数组去重
const arr = [1,2,2,3,3,4,5,5,6];
console.log(new Set(arr));
console.log(arr.filter((item, index) =>
    arr.indexOf(item) === index
))
console.log(arr.reduce((prev,cur)=>
    prev.includes(cur) ? prev : [...prev, cur],[]
))

function noRepeat(arr) {
    for(let i = 0; i < arr.length; i++){
        if(arr.indexOf(arr[i]) !== i){
            arr.splice(i,1);
            i--;
        }
    }
    return arr;
}

// 数组扁平化
function flat(arr) {
    const result = [];
    arr.forEach(item => {
        if(Array.isArray(item))
            result = result.concat(flat(item));
        else
            result.push(item);
    })
    return result;
}

const flat2 = (arr) => {
    return arr.reduce((prev, cur)=>{
        if(Array.isArray(cur))
            return prev.concat(flat2(cur));
        else
            return prev.concat(cur);
    }, []);
}

const flat3 = (arr) => {
    const result = [];
    const stack = arr.slice();
    while(stack.length){
        let val = stack.pop();
        if(Array.isArray(val))
            stack.push(...val);
        else
            result.unshift(); 
    }
    return result;
}

const flat4 = (arr, num=1) => {
    return num > 0 ? arr.reduce(() => {
        return prev.concat(Array.isArray(cur) ? flat4(cur, num) : cur);
    },[]) : arr.slice();
}
